#include <stdio.h>

#include "SqQueue.h"
#include "SqStack.h"
#include "BinaryTree.h"

#include "HuffmanTree.h"

//非递归中序遍历
void inOrder(BinTree &T){
    if(!T)
        return;
    SqStack S;
    init(S);
    //先压入根
    push(S, *T);
    BinTreeNode top;
    while(!isEmpty(S)){
        getTop(S, top);
        if(top.left){
            //栈顶节点left断开
            setTop(S, {top.data, NULL, top.right});
            //压入左节点
            push(S, *(top.left));
        }else{  //无左孩子
            pop(S, top);
            printf("%c\t", top.data);
            if(top.right)
                push(S, *(top.right));
        }
    }
}
//递归后序遍历
void afterOrder(BinTree &T){
    if(!T)
        return;
    afterOrder(T->left);
    afterOrder(T->right);
    printf("%c\t", T->data);
}
//层序遍历
void levelTraversal(BinTree &T){
    SqQueue Q;
    init(Q);
    enter(Q, *T);
    QueElemType top;
    while(!isEmpty(Q)){
        //访问该节点
        remove(Q, top);
        printf("%c\t", top.data);
        //将该节点的左右孩子入队
        if(top.left)
            enter(Q, *(top.left));
        if(top.right)
            enter(Q, *(top.right));
    }
}
/*

输入：
1
2
3
#
#
4
#
#
5
#
#

*/

int main(){
    // BinTree T;
    // create(T);
    // printf("非递归中序遍历:\n");
    // inOrder(T);
    // printf("\n递归后序遍历:\n");
    // afterOrder(T);
    // printf("\n层序遍历:\n");
    // levelTraversal(T);

    HuffmanTree HT;
    HuffmanCode HC;
    int w[8] = {2, 15, 30, 8, 10, 5, 12, 18};
    int n = 8; 

    HuffmanCoding(HT, HC, w, n);
    for(int i = 1; i <= n; i++){
        printf("%s\n", HC[i]);
    }
    return 0;
}
